#include <stdio.h>

//Variaveis para resolucao do problema
int nv;				//Numero de vertices
int na;				//Numero de arestas
int in;				//Numero de nos na MST
int grafo[256];		//Matriz de Adjacencia 16x16 (Maximo de vertices igual a 16)
int intree[16];		//Informa quem ja esta na arvore.
int total;

//Contadores.
int i;
int j;
int k;

//Temporarios
int o, d, p;		//Origem, Destino e Peso

//Arquivo
FILE *file;			//Arquivo de entrada


int main(int argc, char**argv){

	file = fopen("entrada.txt", "r");
	
	fscanf(file, "%d", &nv);
	fscanf(file, "%d", &na);
	
	//Inicializa matriz de adjacencia.
	for(i = 0; i < nv; i++){
		for(j = 0; j < nv; j++){
			if(i == j){
				grafo[i*16 + j] = -1;
			}
			else{
				grafo[i*16 + j] = -1;	//-1 indica que nao existe ligacao entre os pontos indicados.
			}
		}
		
		intree[i] = 0;					//Ninguem esta na MST no inicio.
		
	}
	
	//Faz a leitura das arestas.
	for(i = 0; i < na; i++){
		fscanf(file, "%d", &o);
		fscanf(file, "%d", &d);
		fscanf(file, "%d", &p);
		
		grafo[o*16 + d] = p;
		grafo[d*16 + o] = p;			
	}
	
	fclose(file);
	
	//Executa o algoritmo
	intree[0] = 1;						//O no 0 comeca na MST
	in = 1;								//Um no na MST
	total = 0;							//Valor total da MST
	
						
	
	while(in != nv){													//Enquanto todos os vertices nao estiverem na MST
	
		//Valores para a menor aresta que foi encontrada na arvore.
		o = -1;								
		d = -1;								
		p = 999999;		
	
		for(i = 0; i < nv; i++){										//Procura a menor aresta dos vertices que estao na arvore.
			if(intree[i] == 1){											//Se esse no estiver na arvore.
				for(j = 0; j < nv; j++){								//Verifica as arestas desse no, procurando a menor de todas.
					if((intree[j] == 0) && 								//Se o vertice j nao esta na arvore
						  (grafo[i * 16 + j] >= 0) && 					//Se essa aresta existe
								(grafo[i * 16 + j] < p)){				//Se essa aresta e a menor
						
						//Anota os valores da menor aresta encontrada.
						o = i;
						d = j;
						p = grafo[i * 16 + j];
						
					}
				}
			}
		}
		
		if(o == -1){ break; }			//Se nao foi encontrado nenhuma aresta, entao encerra o algoritmo.
		
		grafo[o * 16 + d] = -2;			//-1 a aresta nao existe -2 a aresta existe e foi escolhida.
		grafo[d * 16 + o] = -2;		
		
		//printf("Inserindo(%d) %d %d = %d\n", intree[d], o, d, p);
		
		total += p;						//Valor da MST incrementado.
		intree[d] = 1;					//Vertice d entra na MST
		in++;							//Numero de vertices na MST incrementado.
	}
	
	
	if(nv == in){						//Se encerrou com todos na MST
	
		//for(i = 0; i < nv; i++){
		//	for(j = 0; j < nv; j++){
		//		printf("%3d ",grafo[i*16 + j]);
		//	}
		//	printf("\n");
		//}
	
		printf("MST Total = %d\n", total);
	}
	else{
		printf("Nao foi possivel adicionar todo mundo na MST\n");
	}

	return 0;
}
